package problem148;

//148.排序链表
//https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        //将链表拆成两半部分 head mid
        ListNode mid = splitMiddle(head);
        //递归
        head = sortList(head);
        mid = sortList(mid);
        //合并两个有序链表
        return merge(head, mid);
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while(head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            }else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if(head1 != null) tail.next = head1;
        if(head2 != null) tail.next = head2;
        return newHead.next;
    }

    private ListNode splitMiddle(ListNode head) {
        ListNode fast = head, slow = head, prev = null;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        prev.next = null;
        return slow;
    }
}